1. Field of the Invention
The present invention relates to method and apparatus for decoding a cyclic code.
2. Description of the Prior Art
A cyclic code is one of the codes for correcting a burst error (having a burst length b) generated in a data transmission line.
A generator polynomial of the cyclic code is expressed by ##EQU2## where P.sub.i (x) is a m.sub.i -order irreducible polynomial. The irreducible polynomial is defined as one which is not divisible without a residue by any polynomial having an order of no less than one and no more than m.sub.i -1. Hereinafter, ##EQU3##
When the number of bits of the data is s and n-m-c.gtoreq.s (where n is a code length of the cyclic code) and c.gtoreq.2b+d-1, any burst error which meets b.ltoreq.m can be corrected. (See "Burst-Correcting Codes with High Speed Decoding" by Robert T. Chien, IEEE Trans. on Information Theory, Vol. IT-15, No. 1, January 1969.)
The code length n of the cyclic code is a least common multiple of a period e.sub.i of P.sub.i (x) and c, that is, LCM (c, e.sub.1, e.sub.2, . . . e.sub.l).
The period e.sub.i of P.sub.i (x) is the order of a minimum order polynomial (1+x.sup.e.sbsp.i) of polynomials which have forms of (1+x.sup..alpha.) and are divisible by P(x) without a residue.
At first an encoding method of the cyclic code is described.
I. Encoding Method of the Cyclic Code
Data D(x) to be transmitted is expressed as EQU D(i x)=a.sub.s-1 .multidot.x.sup.s-1 +a.sub.s-2 .multidot.x.sup.s-2 + . . . +a.sub.o ( 2)
The cyclic code is encoded by expressing a product D(x).multidot.x.sup.m+c such that it is divisible by a generator polynomial G(x) without a residue. The polynomial D(x) represents data (a.sub.s-1, a.sub.s-2, . . . a.sub.o) sent out to the transmission line.
A residue produced when D(x).multidot.x.sup.m+c is divided by G(x) is represented by a check pattern R(x)=R.sub.m+c-1 .multidot.x.sup.m+c-1 +R.sub.m+c-2 .multidot.x.sup.m+c-2 + . . . +R.sub.o (a bit length of the check pattern R(x) is m+c). Thus, EQU D(x).multidot.x.sup.m+c =G(x).multidot.Q(x)+R(x)
where Q(x) is a quotient.
A code word F(x) of the cyclic code is represented by EQU F(x)=D(x).multidot.x.sup.m+c +R(x) (3)
F(x) is divisible by G(x) without a residue and the encoding of the cyclic code is terminated.
A divider for dividing D(x).multidot.x.sup.m+c by G(x) and producing the residue R(x) may be a conventional one.
II. Method of Decoding the Cyclic Code
A receiving station receives a code word F*(x). F*(x) is divided by the generator polynomial. It must be divisible without a residue if no error is included in F*(x). (The transmitted code word F(x) is divisible by G(x) without a residue.) However, if F*(x) includes a burst error B(x) starting from a (j+1)th bit, F*(x) is not divisible by G(x). F*(x) under this condition is represented by EQU F*(x)=F(x)+x.sup.j .multidot.B(x) (4)
The generator polynomial G(x) consists of the polynomial (x.sup.c +1) and the irreducible polynomial P.sub.i (x). Residues produced by dividing F*(x) by those polynomials are syndromes R.sub.c (x) and RPi(x), respectively. Those syndromes are multiplied by x.sup.n-j and the products are divided by (x.sup.c +1) and P.sub.i (x), respectively. If residues are equal, (j+1) represents the error position and x.sup.n-j .multidot.RPi(x) represents the burst error B(x). Accordingly, the followings are met. ##EQU4## Both sides are multiplied by x.sup.n-j and the equations are rewritten as follows. ##EQU5## where x.sup.j .multidot.B(x).ident.R.sub.c (x) (mod P(x)) represents that the residues when divided by P(x) are equal.
Hereinafter, the following generator polynomial G(x) of the cyclic code is assumed. EQU G(x)=(x.sup.22 +1).multidot.(x.sup.12 +x.sup.11 +x.sup.10 + . . . +x+1).multidot.(x.sup.11 +x.sup.7 +x.sup.6 +x+1).multidot.(x.sup.11 +x.sup.9 +x.sup.7 +x.sup.6 +x.sup.5 +x+1) (7) EQU P.sub.1 (x)=x.sup.12 +x.sup.11 +x.sup.10 + . . . +x+1 EQU P.sub.2 (x)=x.sup.11 +x.sup.7 +x.sup.6 +x+1 EQU P.sub.3 (x)=x.sup.11 +x.sup.9 +x.sup.7 +x.sup.6 +x.sup.5 +x+1
In the polynomial (7), (x.sup.12 +x.sup.11 +x.sup.10 + . . . +x+1) divides (x.sup.13 +1) and hence a period of P.sub.i (x) is 13. Periods of the polynomials (x.sup.11 +x.sup.7 +x.sup.6 +x+1) and (x.sup.11 +x.sup.9 +x.sup.7 +x.sup.6 +x.sup.5 +x+1) and 89 and 23, respectively. (See "Code Theory" by H. Miyagawa, Y. Iwadare and H. Imai, edited by Shokodo, page 530). Accordingly, the code length n is LCM (22, 13, 89, 23)=585442, where LCM is a least common multiple. Thus, a single burst error up to 11 bits can be corrected.
FIG. 1 shows a decoder. FSRC denotes a divider which divides the input code F*(x) supplied via a signal line 160 by (x.sup.c +1). FSRP.sub.1, FSRP.sub.2 and FSRP.sub.3 denote dividers which divide the input code F*(x) by the polynomials P.sub.1 (x), P.sub.2 (x) and P.sub.3 (x), respectively. Details thereof will be explained in embodiments of the invention. A coincidence circuit 223 checks bit-by-bit coincidence of low order 11 bits of the FSRC and low order 11 bits of the FSRP.sub.1. Coincidence circuits 324 and 325 check bit-by-bit coincidence of the low order 11 bits of the FSRP.sub.1 and the low order 11 bits of the FSRP.sub.2, and the bits of the FSRP.sub.2 and the bits of the FSRP.sub.3, respectively. A zero detector 326 checks if all of high order 11 bits of the FSRC and high order one bit of the FSRP.sub.1 are zero. When the low order 11 bits of the FSRC, the low order 11 bits of the FSRP.sub. 1, the bits of the FSRP.sub.2 and the bits of the FSRP.sub.3 have bit-by-bit correspondence and the high order 11 bits of the FSRC and the high order one bit of the FSRP.sub.1 are zero, a signal line 171 connected to an output of an AND gate 170 is rendered high level.
When the input code F*(x) has been inputted to the FSRC, FSRP.sub.1, FSRP.sub.2 and FSRP.sub.3, syndromes S.sub.c (x), S.sub.p1 (x), S.sub.p2 (x) and S.sub.p3 (x) therefor meet the following relationships because the input code is inputted to an m'-th stage of respective shift registers (m'=min (m.sub.1, m.sub.2, m.sub.3)). ##EQU6## By multiplying both sides of the equations (8) by x.sup.n-j-m', the left sides become B(x). It represents that all low order m' bits of the FSRC, FSRP.sub.1, FSRP.sub.2 and FSRP.sub.3 are coincident and all bits in higher orders than m' are zero. B(x) represents the error pattern and j represent an error location.
In this prior art decoding method, a maximum of (n-m') times of shifting are necessary to find j.
When such a cyclic code is actually used, a maximum of (n-m') times of shifting are required whatever low the order of the input code F*(x) is.
For example, in a disk data, one sector has 128 bytes (1024 bits) or 256 bytes (2047 bits). On the other hand, in a fire code which uses the generator polynomial G(x) as represented by the formula (7), n=585442 which is approximately 200-500 times as long. Even in this case, approximately 580 thousands times of shifting are required.
In order to reduce the number of times of shifting, it has been proposed to use the "Chinese Remainder Theorem" (See "Burst-Correcting Codes with High Speed Decoding" referenced above.) However, this method requires an integer divider having a divisor n and hence a complex hardware.